#ifndef LEETCODE_CN_CPP_PROBLEMS_20_H
#define LEETCODE_CN_CPP_PROBLEMS_20_H

#include <stack>
#include <string>

using namespace std;

namespace problem_20
{

class Solution
{
private:
    constexpr bool match(char left, char right)
    {
        switch (left)
        {
        case '(':
            return right == ')';
        case '[':
            return right == ']';
        case '{':
            return right == '}';
        default:
            return false;
        }
    }

public:
    bool isValid(string s)
    {
        stack<char> stk;
        for (auto c : s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                stk.push(c);
            }
            else
            {
                if (stk.empty() || !match(stk.top(), c))
                {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty();
    }
};

} // namespace problem_20

#endif //LEETCODE_CN_CPP_PROBLEMS_20_H
